package l.l.w.CodingInterviews;

import java.util.ArrayList;
import java.util.Random;

import static l.l.test.JustStaticField.a;

/**
 * Created by llw on 2018/3/27/0027.
 */
public class 最小的K个数 {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if(input == null || input.length == 0 || k < 0 || k > input.length) return result;
        int start = 0, end = input.length - 1,index = 0;
        Random random = new Random();
        while(start < end){
//            int temp = input[random.nextInt(end - start)+ start];
            int temp = input[start];
            int i = start,j = end, t = start;

            while(i <= j){
                if(input[i] < temp)swap(input,i++,t++);
                else if(input[i] > temp) swap(input,i,j--);
                else i++;
            }
            if( i == k -1) break;
            if( i < k-1){
                start = i + 1;
            } else{
                end = i - 1;
            }
        }
        for(int i = 0; i < k; ++i){
            result.add(input[i]);
        }
        return result;
    }

    private void swap(int a[], int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String[] args) {
        int[] a = {4,5,1,6,2,7,3,8};
        int k = 4;
        ArrayList<Integer> result = new 最小的K个数().GetLeastNumbers_Solution(a, k);

        ArrayList<Integer> result2 = new Solution().GetLeastNumbers_Solution(a, k);
        System.out.println(result2);
        System.out.println(result);
    }
}


class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if (input.length < k) {
            return list;
        }
        findKMin(input, 0, input.length - 1, k);
        for (int i = 0; i < k; i++) {
            list.add(input[i]);
        }
        return list;
    }

    public void findKMin(int[] a, int begin, int end, int k) {
        if (begin < end) {
            int pos = partition(a, begin, end);
            if (pos == k - 1) {
                return;
            } else if (pos < k - 1) {
                findKMin(a, pos + 1, end, k);
            } else {
                findKMin(a, begin, pos - 1, k);
            }
        }
    }

    public int partition(int[] a, int begin, int end) {
        int pivot = a[begin];
        while (begin < end) {
            while (begin < end && a[end] >= pivot) {
                end--;
            }
            ;
            a[begin] = a[end];
            while (begin < end && a[begin] <= pivot) {
                begin++;
            }
            ;
            a[end] = a[begin];
        }
        a[begin] = pivot;
        return begin;
    }
}
